#include "../DataStructures/avdtech.h"
#include "../DataStructures/pq.h"
#include "graph_algos.h"

typedef struct _vertex {
    int v;
    int dist;
} vertex;

int d_key_cmp(const void *a, const void *b) {
    if (((vertex *) a)->dist > ((vertex *) b)->dist) return 1;
    else if (((vertex *) a)->dist < ((vertex *) b)->dist) return -1;

    return 0;
}

void d_data_copy(void *dest, const void *src) {
    vertex *n = (vertex *) dest;
    n->dist = ((vertex *) src)->dist;
    n->v = ((vertex *) src)->v;
}

void dijkstra(GRAPH *g, int start, int dist[], int path[]) {
    PQ pq;
    EDGE *e;
    int v, u;
    vertex n;

    /* initialize single source */
    pq_init(&pq, g->nvertices, sizeof (vertex), d_key_cmp, d_data_copy, NULL, NULL);

    for (v = 1; v <= g->nvertices; v++) {
        dist[v] = 1000010;
        path[v] = -1;
        n.v = v;
        n.dist = dist[v];
        pq_enqueue(&pq, &n, v);
    }

    dist[start] = 0;
    n.v = start;
    n.dist = 0;
    pq_decrease_priority(&pq, &n, start);

    while (!is_pq_empty(&pq)) {
        pq_dequeue(&pq, &n);

        u = n.v;
        e = g->adj[u]; /* for each node (u,v) */
        while (e != NULL) {
            if (dist[e->v] > dist[u] + e->w) {
                dist[e->v] = dist[u] + e->w;
                path[e->v] = u;

                n.v = e->v;
                n.dist = dist[e->v];
                pq_decrease_priority(&pq, &n, n.v);
            }
            e = e->next;
        }
    }

    pq_delete(&pq);
}
